1. Field of the Invention
The current invention relates to performing hash functions, and in particular, to performing hash functions for data authentication.
2. Description of the Related Art
It may sometimes be necessary, for security and/or data integrity, to be able to authenticate and verify stored or transmitted data or messages. Such authentication and verification capabilities may be provided by secret-key-based message-authentication codes (MACs). Keyed-Hashing for Message Authentication Code (HMAC), which uses cryptographic hash functions, is one such mechanism for message authentication and verification. HMAC is described in Request for Comment (RFC) 2104 of the Internet Engineering Task Force (IETF), titled “HMAC: Keyed-Hashing for Message Authentication,” incorporated herein by reference in its entirety.
HMAC may be used to authenticate secure real-time protocol (SRTP) packets. SRTP is a secure version of RTP, where RTP is a protocol for delivering media content over a packet-switched network, such as the Internet. SRTP provides security, integrity, and authentication for RTP packets. Packet authentication and integrity are achieved using HMAC, which is used to produce an authentication tag that is appended to the packet.
HMAC uses a cryptographic hash function, H, and a secret key, K, to generate a hash output of length L bytes from a block text of length B bytes. The length of secret key K should be greater than or equal to L bytes and less than or equal to B bytes; keys that are too short provide insufficient security, while keys that are too long are typically trimmed to length B bytes. HMAC uses an inner padding pad ipad and an outer padding pad opad, where ipad=the byte 0x36 repeated B times and opad=the byte 0x5C repeated B times. The function HMAC for input block text is defined as per Formula (1) below:H((K XOR opad)∥H((K XOR ipad)∥text))  (1)where, ∥ is a concatenation operator and, if key K is shorter than B bytes, then zeroes are appended to the end of key K to create a B-byte string. The steps represented by Equation (1) are performed as follows:
(a) perform a bitwise XOR of key K (with appended zeroes, if needed) and pad ipad;
(b) concatenate the result of step (a) with block text;
(c) apply hash function H to the result of step (b);
(d) perform a bitwise XOR of key K and pad opad;
(e) concatenate the result of step (d) with the result of step (c); and
(f) apply hash function H to the result of step (e).
Note that the steps above do not have to be performed in the above sequence; for example, step (d) may be performed before any of the other steps.
Examples of hash function H include iterative, cryptographic hash functions such as MD5 (message-digest algorithm 5) and SHA-1 (secure hash algorithm 1). HMAC using SHA-1 is typically referred to as HMAC-SHA-1. SHA-1 is described in Federal Information Processing Standards Publication 180-2 (FIPS 180-2), titled “Secure Hash Signature Standard,” published by the National Institute of Standards and Technology (NIST), and incorporated herein by reference in its entirety. SHA-1 is an iterative, one-way hash function that processes a message to produce a condensed representation called a message digest. SHA-1 enables the determination of the message's integrity since a change to the message will very likely result in a change to the corresponding message digest.
Running the SHA-1 algorithm includes two stages: preprocessing and hash computation. Preprocessing includes three steps: (1) padding a message, (2) parsing the padded message into fixed-size blocks, and (3) setting initialization values to be used in the hash computation. The hash computation then generates a message schedule from the padded message and uses that schedule, along with certain functions, constants, and word operations to iteratively generate a series of hash values. The final hash value generated by the hash computation is used to determine the message digest.
SHA-1 operates on 512-bit blocks and, therefore, the padding outputs a padded message whose length in bits is an integer multiple of 512. To pad a message M of length l bits, where 0≦l<264, (a) append the bit “1” to the end of message M, (b) add k zeroes, where k is the smallest non-negative solution to the congruence relation l+1+k≡448 (mod 512), and (c) append a 64-bit block equal to the number l in binary. This resultant padded message has a bit-length that is an integer multiple of 512. Next, the padded message is parsed into N 512-bit blocks referenced as M(1), M(2), . . . M(N). Each block M(i) consists of sixteen 32-bit (4-byte) words referenced as M(i)j, where j runs from 0 to 15. Thus, for example, the second word of the third block would be referenced as M(3)1. The final preprocessing step is setting the initial hash value H(0) to the concatenation of five predetermined 32-bit (4-byte) words H(0)0, H(0)1, H(0)2, H(0)3, and H(0)4.
FIG. 1 shows pseudo-code 100 for Algorithm (2) for the sequential processing of message blocks M(1), M(2), . . . M(N) that is at the core of the hash computation. Algorithm (2) is performed once for each one of the N message-block iterations. The hash computation uses (i) a message schedule {Wt} of eighty 32-bit words W0, W1, . . . W79 and (ii) five working variables, a, b, c, d, and e. Note that ⊕ is a bitwise XOR operator and ROTLn(x) is a rotate-left (circular left shift) operator, which circularly left-rotates word x by n bytes; thus, the first sixteen words of message schedule {Wt} are the sixteen words of block M(i), while the other 64 words of the message schedule are functions of those first sixteen words. In addition, note that ƒt is one of three predefined functions, described below, which outputs a 32-bit word.
Algorithm (2) comprises, for each message block M(i), preparing message schedule {Wt}, initializing the working variables, processing the message block in eighty message-schedule iterations, and updating the hash value H(i). After repeating steps 1 through 4 of Algorithm (2) a total of N times, i.e., after processing the Nth block of M, i.e., M(N), the resulting 160-bit message digest of the message M is H.
Note that the logical function ƒt(x, y, z) is defined as per Formula (3) below:
            f      t        ⁡          (              x        ,        y        ,        z            )        =      {                                                      Ch              ⁡                              (                                  x                  ,                  y                  ,                  z                                )                                      =                                          (                                  x                  ⋀                  y                                )                            ⊕                              (                                                    ⁢                                      x                    ⋀                    z                                                  )                                                                                        for              ⁢                                                          ⁢              0                        ≤            t            ≤            19                                                (            3.1            )                                                                          Parity              ⁡                              (                                  x                  ,                  y                  ,                  z                                )                                      =                          (                              x                ⊕                y                ⊕                z                            )                                                                          for              ⁢                                                          ⁢              20                        ≤            t            ≤            39                                                (            3.2            )                                                                          Maj              ⁡                              (                                  x                  ,                  y                  ,                  z                                )                                      =                                          (                                  x                  ⋀                  y                                )                            ⊕                              (                                  x                  ⋀                  z                                )                            ⊕                              (                                  y                  ⋀                  z                                )                                                                                        for              ⁢                                                          ⁢              40                        ≤            t            ≤            59                                                (            3.3            )                                                                          Parity              ⁡                              (                                  x                  ,                  y                  ,                  z                                )                                      =                          (                              x                ⊕                y                ⊕                z                            )                                                                          for              ⁢                                                          ⁢              60                        ≤            t            ≤            79                                                (            3.4            )                              where  is a bitwise AND operator, ⊕ is a bitwise XOR operator, and  is a bitwise complement operator.Furthermore, note that alternative methods may be used under SHA-1 to come up with the same message digest.
Generating the message digest requires at least 1360 processor operations per 512-byte block and may require an even greater number of clock cycles since some operations require processor stalls between them so as to let data stabilize and prevent certain errors. Novel systems and methods to generate a message digest more efficiently may be useful.